package _08_DFS_BFS;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class _542_01矩阵 {

    private int rows;

    private int cols;

    private int[][] vector = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) {
        int[][] ins = {
                {0, 0, 0},
                {0, 1, 0},
                {1, 1, 1}
        };
        _542_01矩阵 v = new _542_01矩阵();
        int[][] ints = v.updateMatrix(ins);
        for (int[] anInt : ints) {
            System.out.println(Arrays.toString(anInt));
        }
    }

    // 动态规划，如果可以使用前面遍历的值，并且路径不相关，则可以使用动态规划写
    // 并且动态规划如果有多种情况，找最值，也可以遍历多种情况，最值就能找到最优解
    public int[][] updateMatrix(int[][] mat) {
        rows = mat.length;
        cols = mat[0].length;
        int[][] result = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            Arrays.fill(result[i], Integer.MAX_VALUE >> 1);
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (mat[i][j] == 0) {
                    result[i][j] = 0;
                }
            }
        }

        // 动态规划计算 左，上
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i - 1 >= 0) {
                    result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
                }
            }
        }

        // 动态规划计算 左，下
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = 0; j < cols; j++) {
                if (i + 1 < rows) {
                    result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
                }
            }
        }

        // 动态规划计算 右，上
        for (int i = 0; i < rows; i++) {
            for (int j = cols - 1; j >= 0; j--) {
                if (i - 1 >= 0) {
                    result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
                }
                if (j + 1 < cols) {
                    result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
                }
            }
        }

        // 动态规划计算 右，下
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 0; j--) {
                if (i + 1 < rows) {
                    result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
                }
                if (j + 1 < cols) {
                    result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
                }
            }
        }
        return result;
    }

    // 以0位中心
    public int[][] updateMatrix2(int[][] mat) {
        rows = mat.length;
        cols = mat[0].length;
        // 零队列
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[rows][cols];
        int[][] result = new int[rows][cols];
        // 查询0
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
        // 以0为中心，广度优先搜索
        while (!queue.isEmpty()) {
            int[] info = queue.poll();
            // 4个方向开始搜索
            for (int[] ints : vector) {
                int row = info[0] + ints[0];
                int col = info[1] + ints[1];
                if (row >= 0 && row < rows && col >= 0 && col < cols && !visited[row][col]) {
                    result[row][col] = result[info[0]][info[1]] + 1;
                    visited[row][col] = true;
                    // 入队
                    queue.offer(new int[]{row, col});
                }
            }
        }
        return result;
    }

    // 超时
    public int[][] updateMatrix1(int[][] mat) {

        int[][] result = new int[mat.length][mat[0].length];

        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[i].length; j++) {
                if (mat[i][j] == 0) continue;
                // 广度优先搜索离0的最近距离
                result[i][j] = bfs(mat, i, j);
            }
        }
        return result;
    }

    public int bfs(int[][] mat, int row, int col) {
        Deque<MatInfo> queue = new LinkedList<>();
        // 搜索上下左右数据
        queue.offer(new MatInfo(row, col, 0));
        while (!queue.isEmpty()) {
            MatInfo matInfo = queue.poll();
            int rowR = matInfo.row;
            int colR = matInfo.col;
            int level = matInfo.level;
            if (mat[rowR][colR] == 0) {
                return level;
            }
            level++;
            // 上
            if (rowR > 0) {
                queue.offer(new MatInfo(rowR - 1, colR, level));
            }
            // 下
            if (rowR < mat.length - 1) {
                queue.offer(new MatInfo(rowR + 1, colR, level));
            }
            // 左
            if (colR > 0) {
                queue.offer(new MatInfo(rowR, colR - 1, level));
            }
            // 右
            if (colR < mat[rowR].length - 1) {
                queue.offer(new MatInfo(rowR, colR + 1, level));
            }
        }
        return -1;
    }

    private static class MatInfo {

        public int row;

        public int col;

        public int level;

        public MatInfo(int row, int col, int level) {
            this.row = row;
            this.col = col;
            this.level = level;
        }
    }

}
